package solution.math;

import java.util.HashSet;
import java.util.Set;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class SumToValue {

	/**
	 * http://www.sureinterview.com/wiki/Shwqst/98001
	 * 
	 * @param vals
	 * @param sum
	 * @return
	 */
	public boolean getSum4Val(int[] vals, int sum) {
		// a > b > c > d
		// Following set contains all (c + d), where c < b < a and d < b < a.
		Set<Integer> set = new HashSet<Integer>();
		for (int b = 0; b < vals.length; b++) {
			// check if [sum - (a + b)] is in the set.
			for (int a = b + 1; a < vals.length; a++) { // a > b
				Integer key = sum - (vals[a] + vals[b]);
				if (set.contains(key))
					return true;
			}

			// update the set
			int c = b;
			for (int d = 0; d < c; d++) {
				set.add(vals[c] + vals[d]);
			}
		}
		return false;
	}

	@Test
	public void test() {
		int[][] vals = new int[][] {//
		//
				{ 1 }, { 0, 0, 0, 1 },//
				{ 10 }, { 1, 2, 3, 4 },//
				{ 10 }, { 1, 2, 3, 4, 5 },//
				{ 10 }, { 1, 2, 3, 5, 4 },//
				{ 10 }, { 1, 2, 5, 3, 4 },//
				{ 10 }, { 5, 1, 2, 3, 4, 5 },//
		};

		for (int i = 0; i < vals.length; i += 2) {
			Assert.assertTrue(getSum4Val(vals[i + 1], vals[i][0]));
		}

		vals = new int[][] {//
		//
				{ 1 }, { 0, 0, 0, 0 },//
				{ 10 }, { 1, 2, 3, 3, 10 },//
				{ 10 }, { 1, 2, 3, 3, -1 },//
		};
		for (int i = 0; i < vals.length; i += 2) {
			Assert.assertFalse(getSum4Val(vals[i + 1], vals[i][0]));
		}
	}
}
